package com.Questions.DFS;

import java.util.*;
public class leetcode508 {
    Map<Integer,Integer> map=new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        traveTree(root);
        ArrayList<Integer> list=new ArrayList<>();
        int max=0;
        for(Integer key:map.keySet()){
            if(map.get(key)>max){
                list.clear();
                list.add(key);
                max=map.get(key);
            }else if(map.get(key)==max){
                list.add(key);
            }
        }
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();++i){
            res[i]= list.get(i);
        }
        return res;
    }
    public int traveTree(TreeNode root){
        if(root.left==null&&root.right==null){
            map.put(root.val,map.getOrDefault(root.val,0)+1);
            return root.val;
        }
        int leftSum=0;
        int rightSum=0;
        if(root.left!=null){
            leftSum=traveTree(root.left);

        }
        if(root.right!=null){
            rightSum=traveTree(root.right);
        }
        map.put(leftSum+rightSum+root.val,map.getOrDefault(leftSum+rightSum+root.val,0)+1);
        return leftSum+rightSum+root.val;
    }

}
